1. Field of the Invention
The present invention relates to the design of computer systems that support references to objects defined within an object-oriented programming system. More specifically, the present invention relates to an object addressing scheme that avoids collisions between cache lines containing objects and cache lines containing corresponding object table entries.
2. Related Art
As object-oriented programming languages become more widely used, computer systems are being designed to manipulate objects more efficiently. Note that in order to manipulate objects, computer systems also manipulate ancillary data structures associated with objects. For example, each object in an object-oriented programming system is typically associated with an object table entry that contains metadata associated with the object, such as the object's physical address (if the object has one).
Hence, in order to access the object it may be necessary to first access the object table entry for the object to determine the physical address of the object. This process is outlined in FIG. 1 which illustrates how a computer system uses an object identifier (OID) 104 to reference an object table entry (OTE) 108 from an object table 106. (Note that object table 106 also contains entries for other objects.) Next, the computer system retrieves a physical address 110 for the object from object table entry 108 and uses the physical address 110 to access the object 102 in physical memory 112.
Note that this process for accessing an object can be performed within an object-addressed memory hierarchy, wherein objects can be accessed through object identifiers in cache memory, but are otherwise accessed through corresponding physical addresses in physical memory.
There are a number of different ways to implement object table 106 within an object-addressed memory hierarchy. (1) Object table 106 can be implemented as a table in physical memory 112. However, note that object table 106 is a fixed fraction of the size of the entire object address space, which means that it can potentially occupy a large amount of memory. Hence, it is typically impractical to dedicate such a large portion of physical memory 112 to object table 106. (2) Alternatively, object table 106 can be implemented as a table in virtual memory. However, this requires the object translation process to understand and manipulate page tables, which can introduce additional complexity and delay into the address translation process. (3) A more attractive option is to embed the object table itself into objects. In this way the translation process only needs to perform one type of operation.
Unfortunately, accesses to the object table can potentially interfere with accesses to corresponding objects. In particular, it is possible for object table entries and objects to interfere with each other in a cache. Referring to FIG. 1, if a cache line for an object 102 maps to the same cache set 116 in cache 114 as a cache line for corresponding object table entry 108, some problems can occur. For example, the computer system may frequently need to manipulate the object 102 and its object table entry 108 together, without adversely affected performance if they cannot reside in the cache at the same time.
Hence, what is needed is a method and an apparatus for avoiding interference between cache lines containing objects and cache lines containing corresponding object table entries.